package graph.maze;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author : Rookie
 * @description :
 * @date : 2023/6/25
 */
public class MazeBFS {

    private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右四个方向

    private int[][] maze;

    private boolean[][] visited;

    private Point start;

    private Point end;

    private Queue<Point> path;

    public MazeBFS(int [][]maze,Point start,Point end) {
        this.maze = maze;
        this.visited = new boolean[maze.length][maze[0].length];
        this.start = start;
        this.end = end;
        this.path = new LinkedList<>();
    }

    public void searchBfs() {
        // 将起点加入队列
        this.path.offer(start);
        this.visited[start.x][start.y] = true;

        while (!path.isEmpty()) {
            Point point = path.poll();
            // 如果是终点
            if (point.x == end.x && point.y == end.y) {
                return;
            }

            for (int[] direction : DIRECTIONS) {
                int nextX = direction[0] + point.x;
                int nextY = direction[1] + point.y;
                if (isValidMove(nextX, nextY)) {
                    path.offer(new Point(nextX, nextY));
                    visited[nextX][nextY] = true;
                }
            }
        }
    }

    private boolean isValidMove(int x,int y) {
        if (x < 0 || x >= maze.length || y < 0 || y >= maze[0].length) {
            // 超出边界
            return false;
        }
        // 障碍物或已经访问过
        return maze[x][y] != 1 && !visited[x][y];
    }

    public static void main(String[] args) {
        int[][] maze = {
                {0, 0, 0, 0, 0},
                {0, 1, 1, 0, 0},
                {0, 0, 1, 1, 0},
                {0, 1, 0, 0, 0},
                {0, 0, 0, 1, 0}
        };
        MazeBFS mazeBFS = new MazeBFS(maze, new Point(0, 0), new Point(4, 4));
        mazeBFS.searchBfs();
    }
}
